/* A,B两个单链表递增有序，从A，B中找出公共元素并存放于A链表中 */
#include <iostream>
#include "headfun.h"
using namespace std;

// 将公共元素合并进链表A
void Union(LNode *&A, LNode *&B)
{
  // 指向两个链表
  LNode *p = A->next;
  LNode *q = B->next;
  
  // 辅助指针
  LNode *ra = A, *u;
  
  // 遍历两个链表
  while (p != NULL && q != NULL)
  {
    // A结点数值更小，释放结点
    if (p->data < q->data)
    {
      u = p;
      p = p->next;
      free(u);
    }
    
    // B结点数值更小，释放结点
    else if (p->data > q->data)
    {
      u = q;
      q = q->next;
      free(u);
    }
    
    // 两结点数值一样
    else
    {
      // A的结点添加进链表C
      ra->next = p;
      ra = p;
      
      // 下一个结点
      p = p->next;
      
      // 释放B的结点
      u = q;
      q = q->next;
      free(u);
    }
  }
  
  // 链表A没有遍历完 -- 继续释放结点
  while (p != NULL)
  {
    u = p;
    p = p->next;
    free(u);
  }
  
  // 链表B没有遍历完 -- 继续释放结点
  while (q != NULL)
  {
    u = q;
    q = q->next;
    free(u);
  }
  ra->next = NULL;
  free(q);
}

int main()
{
  // 创建两个链表
  cout << " 链表A:";
  LNode *A = head_Linklist();
  cout << " 链表B:";
  LNode *B = head_Linklist();
  
  // 共同元素合并进链表A
  Union(A, B);
  
  // 打印信息
  LNode *q = A->next;
  while (q != NULL)
  {
    cout << q->data << " ";
    q = q->next;
  }
  return 0;
}